def h(n,k):
    return n%k

k=10
TH=[0]*k
TD=[[None,0]]

# TH = [0,0,0,0,0,0,0,0,0,0]
# TD = [[None,0]]

# Insert(22,'vingt-deux')
# h(22,10) = 2  => ih = 2
#               => TH[2] = 0 donc aucun enregistrement
#               => On ajoute [22,'vingt-deux',0] à TD
#               => TD = [[None,1],[22,'vingt-deux',0]]
#               => index dans TD = 1
#               => TH[2] = 1
#               => TH = [0,0,1,0,0,0,0,0,0,0]

# Insert(24,'vingt-quatre)
# h(24,10) = 4  => ih = 4
#               => TH[4] = 0 donc aucun enregistrement
#               => On ajoute [24,'vingt-quatre',0] à TD
#               => TD = [[None,1],[22,'vingt-deux',0],[24,'vingt-quatre',0]]
#               => index dans TD = 2
#               => TH[4] = 2
#               => TH = [0,0,1,0,2,0,0,0,0,0]

# Insert(53,'test')
# h(53,10) = 3  => ih = 3
#               => TH[3] = 0 donc aucun enregistrement
#               => On ajoute [53,'test',0] à TD
#               => TD = [[None,1],[22,'vingt-deux',0],[24,'vingt-quatre',0],[53,'test',0]]
#               => index dans TD = 3
#               => TH[3] = 3
#               => TH = [0,0,1,3,2,0,0,0,0,0]


def insere(cle,valeur):
    # Calcul de l'indice dans la table de hachage
    ih = h(cle,k)

    # Si aucune valeur n'a été enregistré à cet emplacement
    if TH[ih] == 0:
        TD.append([cle,valeur,0])
        TH[ih] = len(TD)-1
        TD[0][1] = TH[ih]
    # Sinon si une valeur est déjà enregistrée
    else:
        # Récupère l'id du débordement dans TH
        id_debord = TH[ih]

        # Scanne les clés enregistrées
        valeur_remplacee = False
        id_debord_1 = 0
        while id_debord != 0:
            # Récupère la clé
            cle_TD = TD[id_debord][0]
             # Si la clé est déjà dans TD
            if cle_TD == cle:
                # Alors enregistre la nouvelle valeur
                TD[id_debord][1] = valeur    # Enregistre la nouvelle valeur
                valeur_remplacee = True
                break
            # Sinon, récupère l'id_suivant et la clé suivante
            else:
                id_suivant = TD[id_debord][2]
                id_debord_1 = id_debord
                id_debord = id_suivant
                cle_TD = TD[id_debord][0]

        # Si à la fin du scanne on n'a pas remplacé de valeur
        if valeur_remplacee == False:
            # alors on ajoute la nouvelle valeur
            TD.append([cle,valeur,0])

            # met à jour l'id_suivant
            TD[id_debord_1][2]=len(TD)-1

            # met à jour le [None,X] dans TD
            TD[0][1] = TD[id_debord_1][2]

    return TH, TD


# n entiers aléatoires => répartis en n/k dans chaque seau
# donc O(n/k)
def recherche(cle):
    # Calcul de l'indice dans la table de hachage
    ih = h(cle,k)

    # Recherche de la clé
    id = TH[ih]
    if id != 0:
        cle_TH = TD[id][0]
        while cle_TH != cle:
            id_suivant = TD[id][2]
            if id_suivant == 0:
                return False
            else:
                cle_TH = TD[id_suivant][0]
                id = id_suivant
        return True
    else:
        return False

def supprime(cle):
    # Calcul de l'indice dans la table de hachage
    ih = h(cle,k)

    ih = h(cle,k)
    id = TH[ih]
    id_precedent = -1
    if id != 0:
        cle_TH = TD[id][0]
        while cle_TH != cle:
            id_suivant = TD[id][2]
            if id_suivant == 0:
                return False
            else:
                cle_TH = TD[id_suivant][0]
                id_precedent = id
                id = id_suivant

        # id contient l'indice ou se trouve la clé

        # Remplace la clé par None
        TD[id][0] = None

        # Met à jour l'id_suivant précédédent
        # dans TD par l'id suivant de la clé supprimée
        if id_precedent != -1:
            TD[id_precedent][2] = TD[id][2]
        else:
            # Met à jour l'id dans TH
            TH[ih] = 0

        return TH, TD
    else:
        return False